package cn.com.forever.array;

import java.util.ArrayList;
/*
    给定一个数组，找出其中最小的K个数。例如数组元素是4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4。
    0 <= k <= input.length <= 10000
0    <= input[i] <= 10000
 */
public class GetLeastNumbers_Solution {
    public static void main(String[] args) {
    int[] arr = {4,5,1,6,2,7,3,8};
    ArrayList<Integer> list = GetLeastNumbers_solution(arr,4);
        for (int i = 0; i < list.size(); i++) {
            System.out.println(list.get(i));
        }
    }

    public static  ArrayList<Integer> GetLeastNumbers_solution(int [] input, int k) {
        if(input.length < k){
            return new ArrayList<>(0);
        }
        quicksort(input,0,input.length-1);
        ArrayList<Integer> list = new ArrayList<Integer>();
        for (int i = 0; i < k; i++) {
            list.add(input[i]);
        }
        return list;
    }
    public static int[] quicksort(int[] arr,int low,int high){
        if(low > high){
            return null;
        }
        int i = low;
        int j = high;
        int key = arr[low];
        while(i < j){
            while(i < j && arr[j] > key){
                j--;
            }
            if(i < j){
                arr[i] = arr[j];
                i++;
            }
            while(i < j && arr[i] < key){
                i++;
            }
            if(i < j){
                arr[j] = arr[i];
                j--;
            }
        }
        arr[i] = key;
        quicksort(arr,low,i-1);
        quicksort(arr,i+1,high);
        return arr;
    }
}
